#include "StdAfx.h"
#include "MaxHeap.h"
#include "RelatedFun.h"

namespace WTB{

	CMaxHeap::CMaxHeap(void)
	{
	}

	CMaxHeap::~CMaxHeap(void)
	{
	}


	void CMaxHeap::ShiftUpHeap(unsigned _uHoleIndex, CAbstractHeapNode* _pNode){
		unsigned uParentIndex = (_uHoleIndex - 1) / 2;
		while(_uHoleIndex && _pNode->Greater(m_arrNodePoint[uParentIndex])){
			(m_arrNodePoint[_uHoleIndex] = m_arrNodePoint[uParentIndex])->SetHeapIndex(_uHoleIndex);
			_uHoleIndex = uParentIndex;
			uParentIndex = (_uHoleIndex - 1) / 2;
		}
		(m_arrNodePoint[_uHoleIndex] = _pNode)->SetHeapIndex(_uHoleIndex);
	}

	void CMaxHeap::ShiftDownHeap(unsigned _uHoleIndex, CAbstractHeapNode* _pNode){
		unsigned uChildIndex = 2 * (_uHoleIndex + 1);
		while(uChildIndex <= m_uCurrentHeapSize){
			uChildIndex -= (uChildIndex == m_uCurrentHeapSize ||
				m_arrNodePoint[uChildIndex - 1]->Greater(m_arrNodePoint[uChildIndex]));
			if (m_arrNodePoint[uChildIndex]->Greater(_pNode))
			{
				(m_arrNodePoint[_uHoleIndex] = m_arrNodePoint[uChildIndex])->SetHeapIndex(_uHoleIndex);
				_uHoleIndex = uChildIndex;
				uChildIndex = 2 * (_uHoleIndex + 1);
			}else{
				break;
			}
		}
		ShiftUpHeap(_uHoleIndex,_pNode);
	}

}